package 中等.栈;

/**
 * 给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、
 * 非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件
 * 的子数组的个数。
 * 生成的测试用例保证结果符合 32-bit 整数范围。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum
 */
public class 区间子数组个数_795 {

    public static void main(String[] args) {

        System.out.println(numSubarrayBoundedMax2(new int[]{16, 69, 88, 85, 79, 87, 37, 33, 39, 34}, 55, 57));

    }

    /**
     * 模拟（超时）
     */
    public static int numSubarrayBoundedMax(int[] nums, int left, int right) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int curMax = nums[i];
            for (int j = i; j >= 0; j--) {
                if (curMax > right) {
                    break;
                }
                curMax = Math.max(curMax, nums[j]);
                if (curMax >= left && curMax <= right) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 遍历，计算每一个以 nums[i] 为右端点贡献的子数组个数
     * 需要维护 i 之前 left>=nums[j]&&nums[j]<=right 的 j 索引
     * 和 nums[r] > right 的 r 索引
     * 即 [r+1,i]... [j,i] 都是符合条件的以 i 为右端点的子数组
     * 数量为 j-r
     * 注意：
     * 可能存在 j < r 的情况，说明不存在符号条件的子数组
     */
    public static int numSubarrayBoundedMax2(int[] nums, int left, int right) {
        int count = 0;
        int j = -1, r = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= left && nums[i] <= right) {
                j = i;
            }
            if (nums[i] > right) {
                r = i;
            }
            count += Math.max(0, j - r);
        }
        return count;
    }

    // TODO 单调栈

}
